public class Test1 {

     public class ListNode {
         int val;
         ListNode next = null;
         public ListNode(int val) {
             this.val = val;
        }
     }

    public boolean isPail (ListNode head) {
        // write code here
        if (head == null || head.next == null) {
            return true;
        }

        //结点个数
        int count = 0;

        ListNode cur = head;

        while (cur != null) {
            count++;
            cur = cur.next;
        }

        cur = head;

        for (int i = 0; i < (count - count / 2); i++) {
            cur = cur.next;
        }

        //创建新链表
        ListNode newList = new ListNode(cur.val);

        cur = cur.next;
        //头插
        while (cur != null) {
            ListNode newNode = new ListNode(cur.val);
            newNode.next = newList;
            newList = newNode;
            cur = cur.next;
        }

        cur = head;
        while (newList != null) {
            if (newList.val != cur.val) {
                return false;
            }
            newList = newList.next;
            cur = cur.next;
        }

        return true;

    }
}
